/**
 * @param {string} s
 * @return {number}
 */
// 枚举开头，然后枚举结束，结束大于等于开头
// 递归结束条件，枚举位置和字符串长度相等，说明最后一个字符已经选中
var partition = function (s) {
    let ans = []
    let path = []
    let n = s.length
    const dfs = (index) => {
        if(index === n) {
            ans.push(path.concat())
            return
        }
        for(let j = index; j < n; j++) {
            if(isPalindrome(s, index, j)) {
                path.push(s.substring(index, j + 1))
                dfs(j + 1)
                path.pop()
            }
        }
    }
    dfs(0)
    return ans
}
function isPalindrome(s, left, right) {
    while (left < right) {
        if (s[left] !== s[right]) return false
        left++
        right--
    }
    return true
}